import "babel-polyfill";

const {floor, random} = Math;

var default_compare = function(x, y) {
    x = String(x);
    y = String(y);
    if (x === y) {
        return 0;
    } else if (x < y) {
        return -1;
    } else {
        return 1;
    }
};

export var binarySearch = function(value, compare = default_compare) {
    var left = 0, right = this.length - 1;
    while (left <= right) {
        let mid = (left + right) >>> 1;
        let comparison = compare(this[mid], value);
        if (comparison === 0) {
            return mid;
        } else if (comparison < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};

export var randomShuffle = function() {
    for (let i = 1; i < this.length; ++i) {
        let index = floor((i + 1) * random());
        [this[i], this[index]] = [this[index], this[i]];
    }
    return this;
};

export var islice = function*(start = 0, stop = Infinity) {
    var length = this.length;
    if (start <= -length) {
        start = 0;
    } else if (start < 0) {
        start += length;
    } else if (start > length) {
        start = length;
    }
    if (stop <= -length) {
        stop = 0;
    } else if (stop < 0) {
        stop += length;
    } else if (stop > length) {
        stop = length;
    }
    for (let i = start; i < stop; ++i) {
        if (this.hasOwnProperty(i)) {
            yield this[i];
        }
    }
};

export var sort = function({begin = 0, end = Infinity, compare} = {}) {
    var length = this.length;
    if (begin <= -length) {
        begin = 0;
    } else if (begin < 0) {
        begin += length;
    } else if (begin > length) {
        begin = length;
    }
    if (end <= -length) {
        end = 0;
    } else if (end < 0) {
        end += length;
    } else if (end > length) {
        end = length;
    }
    var array = this.slice(begin, end).sort(compare);
    for (let i = begin; i < end; ++i) {
        this[i] = array[i - begin];
    }
    return this;
};

var partition = function(value, {begin = 0, end = Infinity, compare} = {}) {
    var less_than = compare ? (x, y) => compare(x, y) < 0 : (x, y) => String(x) < String(y);
    var greater_than = compare ? (x, y) => compare(x, y) > 0 : (x, y) => String(x) > String(y);
    if (end === Infinity) {
        end = this.length - 1;
    }
    while (true) {
        while (less_than(this[begin], value)) {
            ++begin;
        }
        while (greater_than(this[end], value)) {
            --end;
        }
        if (begin < end) {
            [this[begin], this[end]] = [this[end], this[begin]];
            ++begin;
            --end;
        } else {
            break;
        }
    }
    return begin;
};

export var nthElement = function(n, compare) {
    var array = this.slice();
    var [left, right] = [0, array.length - 1];
    var less_than = compare ? (x, y) => compare(x, y) < 0 : (x, y) => String(x) < String(y);
    var greater_than = compare ? (x, y) => compare(x, y) > 0 : (x, y) => String(x) > String(y);
    while (true) {
        if (n === left) {
            let result = array[left];
            for (let i = left + 1; i <= right; ++i) {
                if (less_than(array[i], result)) {
                    result = array[i];
                }
            }
            return result;
        } else if (n === right) {
            let result = array[left];
            for (let i = left + 1; i <= right; ++i) {
                if (greater_than(array[i], result)) {
                    result = array[i];
                }
            }
            return result;
        } else {
            let place = floor(random() * (right - left + 1)) + left;
            [array[place], array[right]] = [array[right], array[place]];
            place = array::partition(array[right], {begin: left, end: right - 1, compare});
            [array[place], array[right]] = [array[right], array[place]];
            if (n === place) {
                return array[place];
            } else if (n < place) {
                right = place - 1;
            } else {
                left = place + 1;
            }
        }
    }
};

export var nthElementPartition = function(n, compare) {
    var [left, right] = [0, this.length - 1];
    var less_than = compare ? (x, y) => compare(x, y) < 0 : (x, y) => String(x) < String(y);
    var greater_than = compare ? (x, y) => compare(x, y) > 0 : (x, y) => String(x) > String(y);
    while (true) {
        if (n === left) {
            let index = left;
            let result = this[left];
            for (let i = left + 1; i <= right; ++i) {
                if (less_than(this[i], result)) {
                    index = i;
                    result = this[i];
                }
            }
            [this[left], this[index]] = [this[index], this[left]];
            return this;
        } else if (n === right) {
            let index = right;
            let result = this[right];
            for (let i = left; i < right; ++i) {
                if (greater_than(this[i], result)) {
                    index = i;
                    result = this[i];
                }
            }
            [this[right], this[index]] = [this[index], this[right]];
            return this;
        } else {
            let place = floor(random() * (right - left + 1)) + left;
            [this[place], this[right]] = [this[right], this[place]];
            place = this::partition(this[right], {begin: left, end: right - 1, compare});
            [this[place], this[right]] = [this[right], this[place]];
            if (n === place) {
                return this;
            } else if (n < place) {
                right = place - 1;
            } else {
                left = place + 1;
            }
        }
    }
};

export var partialSort = function(n, compare) {
    return this::nthElementPartition(n, compare)::sort({end: n, compare});
};
